import java.util.ArrayList;
import java.util.List;

public class Solution282 {
    List<String> res;

    public List<String> addOperators(String num, int target) {
        res = new ArrayList<>();
        List<Long> nums = new ArrayList<>();
        nums.add((long) num.charAt(0) - '0');
        List<Character> operators = new ArrayList<>();
        dfs(num, 1, nums, operators, nums.get(0), target);
        return res;
    }

    void dfs(String s, int i, List<Long> nums, List<Character> operators, long num, int target) {
        if (i == s.length()) {
            if (num == target) {
                StringBuilder expression = new StringBuilder();
                for (int j = 0; j < nums.size() - 1; j++) {
                    expression.append(nums.get(j)).append(operators.get(j));
                }
                expression.append(nums.get(nums.size() - 1));
                res.add(expression.toString());
            }
            return;
        }

        int n = operators.size();
        int digit = s.charAt(i) - '0';
        long pre = nums.get(n);
        long t = (n > 0 && operators.get(n - 1) == '-') ? -pre : pre;

        nums.add((long) digit);
        operators.add('*');
        dfs(s, i + 1, nums, operators, num - t + t * digit, target);

        operators.set(n, '+');
        dfs(s, i + 1, nums, operators, num + digit, target);

        operators.set(n, '-');
        dfs(s, i + 1, nums, operators, num - digit, target);

        operators.remove(n);
        nums.remove(n + 1);

        if (pre != 0) {
            nums.set(n, pre * 10 + digit);
            long nextNum;
            if (t < 0) {
                nextNum = num + pre - (pre * 10 + digit);
            } else {
                nextNum = num - pre + (pre * 10 + digit);
            }
            dfs(s, i + 1, nums, operators, nextNum, target);
            nums.set(n, pre);
        }
    }
}
